#include <iostream>
using namespace std;
const int N = 1000010;
int n, k;
int a[N], q[N]; // a[]存储数组，q[]存储目前的滑块队列坐标（单调增）
int main()
{
    scanf("%d %d", &n, &k);     // 输入数组和窗口长度
    for (int i = 0; i < n; i++) // 输入队列
        scanf("%d", &a[i]);

    int hh = 0, tt = -1;        // hh队首（左） tt队尾（右）
    for (int i = 0; i < n; i++) // i指向新点
    {
        if (hh <= tt && i - k + 1 > q[hh])   // 队列非空并判断队头是否已经是否已经滑出窗口
            hh++;                            // 队首退出一位（向右）
        while (hh <= tt && a[q[tt]] >= a[i]) // 队列非空并判断目前队尾的值是否大于新加进来的值（确保队列递增）
            tt--;                            // 消去该点队尾（下一步覆盖）
        q[++tt] = i;                         // 插入新队列
        if (i >= k - 1)
            printf("%d ", a[q[hh]]); // 到达滑块范围后打印最小数（由于单调增所以在队列的最左边）
    }
    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > q[hh])
            hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) // 队列非空并判断目前队尾的值是否小于新加进来的值（确保队列递增）
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]);
    }
    puts("");
    
    return 0;
}